package com.LeeCode;

import java.util.HashMap;

/**
 * 从前序与中序遍历序列构造二叉树
 */

public class Code105 {

    public static void main(String[] args) {
        int[] preorder = {-1}, inorder = {-1};
        TreeNode root = new Code105().buildTree(preorder, inorder);
    }

    public HashMap<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        for (int i = 0; i < len; i++) {
            map.put(inorder[i], i);
        }
        TreeNode root = build(preorder, inorder, 0, len - 1, 0, len - 1);
        return root;
    }

    public TreeNode build(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preorder_left]);
        int root_index = map.get(preorder[preorder_left]);
        int num_left = root_index - inorder_left;
        root.left = build(preorder, inorder, preorder_left + 1, preorder_left + num_left, inorder_left, root_index - 1);
        root.right = build(preorder, inorder, preorder_left + num_left + 1, preorder_right, root_index + 1, inorder_right);
        return root;
    }
}
